package com.justnow.offer;

import com.sun.scenario.effect.impl.sw.java.JSWColorAdjustPeer;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @author justnow
 * Created on 2020-09-04
 * Description
 * 剑指 Offer 38. 字符串的排列
 *
 */
public class Solution20 {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    private void dfs(int x) {
        //x 表示需要固定的位置
        if (x == c.length - 1) {
            res.add(String.valueOf(c)); //添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < c.length; i++) {
            if (set.contains(c[i]))
                continue; //重复，因此减剪枝
            set.add(c[i]);
            swap(i, x); //交换，将c[i]固定在第x位
            dfs(x + 1); //开启固定第x + 1位字符
            swap(i, x); // 恢复交换
        }
    }
    private void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }

    public static void main(String[] args) {
        Solution20 solution20 = new Solution20();
        String[] strarray = solution20.permutation("abcd");
        for (String s : strarray) {
            System.out.println(s);
        }
    }
}
